
package v2store

import (
	"path"
	"sort"
	"time"

	"go.etcd.io/etcd/server/v3/etcdserver/api/v2error"

	"github.com/jonboulle/clockwork"
)

// 比较函数结果说明
const (
	CompareMatch = iota
	CompareIndexNotMatch
	CompareValueNotMatch
	CompareNotMatch
)

var Permanent time.Time

// 结构体node是v2版本存储中最基本的元素，
// v2版本存储是树形结构的，node既可以表示其中的一个键值对（叶子节点），
// 也可以表示一个目录（非叶子节点）。
type node struct {
	Path string	// 当前节点的路径，格式类似“／dirl/dir2/key”。
	CreatedIndex  uint64	// 记录创建当前节点时对应的Currentlndex值。
	ModifiedIndex uint64	// 记录最后一次更新当前节点时对应的Currentlndex值。
	Parent *node `json:"-"` // 指向父节点的指针。
	// 	当前节点的过期时间，如果该字段被设置为0，则表示当前节点是一个“永久节点”（即不会被过期删除〉。
	//	node.IsPermanent（）方法通过检查该字段判断当前节点是否为“永久节点”。
	ExpireTime time.Time
	Value      string           // 如果当前节点表示一个键值对，则该字段记录了对应的值。
	// 如果当前节点表示一个目录节点，则该字段记录了其子节点。
	// node.IsDir（）方法通过检查该字段判断当前节点是否为目录节点。
	Children   map[string]*node // 对于目录
	store *store	// 记录当前节点关联的v2版本存储实例。
}

// 对于键值对和目录两种不同类型的节点，v2版本存储分别提供了newKV（）和newDir（）两个不同的函数进行创建，
// 这两个函数会创建node实例并初始化相应的字段
func newKV(store *store, nodePath string, value string, createdIndex uint64, parent *node, expireTime time.Time) *node {
	return &node{
		Path:          nodePath,
		CreatedIndex:  createdIndex,
		ModifiedIndex: createdIndex,
		Parent:        parent,
		store:         store,
		ExpireTime:    expireTime,
		Value:         value,
	}
}

// 对于键值对和目录两种不同类型的节点，v2版本存储分别提供了newKV（）和newDir（）两个不同的函数进行创建，
// 这两个函数会创建node实例并初始化相应的字段
func newDir(store *store, nodePath string, createdIndex uint64, parent *node, expireTime time.Time) *node {
	return &node{
		Path:          nodePath,
		CreatedIndex:  createdIndex,
		ModifiedIndex: createdIndex,
		Parent:        parent,
		ExpireTime:    expireTime,
		Children:      make(map[string]*node),
		store:         store,
	}
}

// node.IsHidden()方法判断某个节点是否为“隐藏节点”，
func (n *node) IsHidden() bool {
	_, name := path.Split(n.Path)	// 按照最后一个“／”符号进行切分，获取节点所在的目录以及节点名称
	return name[0] == '_'	// 检查当前节点是否以下画线开头
}

// IsPermanent函数检查节点是否为永久节点。
func (n *node) IsPermanent() bool {
	// 我们使用未初始化的时间。表示节点为
	// 永久节点的时间。
	// 未初始化的时间。时间应该等于零。
	return n.ExpireTime.IsZero()
}

// IsDir函数检查节点是否为目录。
// 如果节点是目录，则函数返回true。
// 否则函数将返回false。
func (n *node) IsDir() bool {
	return n.Children != nil
}

// 对于键值对节点，node提供了Read（）和Write（）方法用来读写对应的值，
// 需要注意的是，只能读写键值对节点，
func (n *node) Read() (string, *v2error.Error) {
	if n.IsDir() {	// 如果当前节点是目录节点，则抛出异常
		return "", v2error.NewError(v2error.EcodeNotFile, "", n.store.CurrentIndex)
	}

	return n.Value, nil	// 返回Value
}

// 对于键值对节点，node提供了Read（）和Write（）方法用来读写对应的值，
// 需要注意的是，只能读写键值对节点，
func (n *node) Write(value string, index uint64) *v2error.Error {
	if n.IsDir() {	// 如果当前节点是目录节点，则抛出异常
		return v2error.NewError(v2error.EcodeNotFile, "", n.store.CurrentIndex)
	}

	n.Value = value	// 更新值
	n.ModifiedIndex = index	// 记录更新时对应的Currentindex值

	return nil
}

// node.expirationAndTTL（）方法提供了计算当前节点存活时间的功能
func (n *node) expirationAndTTL(clock clockwork.Clock) (*time.Time, int64) {
	if !n.IsPermanent() {	// 检查当前节点是否为永久节点
		/* compute ttl as:
		   ceiling( (expireTime - timeNow) / nanosecondsPerSecond )
		   which ranges from 1..n
		   rather than as:
		   ( (expireTime - timeNow) / nanosecondsPerSecond ) + 1
		   which ranges 1..n+1
		*/
		// 节点过期时间减去当前时间，即为剩余的存活时间
		ttlN := n.ExpireTime.Sub(clock.Now())
		ttl := ttlN / time.Second
		if (ttlN % time.Second) > 0 {	// 以秒为单位，不足一秒则按一秒算
			ttl++
		}
		t := n.ExpireTime.UTC()
		return &t, int64(ttl)	// 返回当前节点的过期时间和剩余存活时间
	}
	return nil, 0	// 永久节点对应的返回值
}

// node.List（）方法主要负责获取当前节点（目录节点）的子节点，
func (n *node) List() ([]*node, *v2error.Error) {
	// 检测当前节点是否为目录节点，如采当前节点不是目录节点，则抛出异常
	if !n.IsDir() {
		return nil, v2error.NewError(v2error.EcodeNotDir, "", n.store.CurrentIndex)
	}

	nodes := make([]*node, len(n.Children))

	i := 0
	for _, node := range n.Children {	// 获取子节点
		nodes[i] = node
		i++
	}

	return nodes, nil
}

// GetChild（）方法获取指定的子节点，该方法直接从Child字段中获取相应的节点，
func (n *node) GetChild(name string) (*node, *v2error.Error) {
	if !n.IsDir() {
		return nil, v2error.NewError(v2error.EcodeNotDir, n.Path, n.store.CurrentIndex)
	}

	child, ok := n.Children[name]

	if ok {
		return child, nil
	}

	return nil, nil
}

// Add（）方法的主要功能是在当前节点下添加子节点，
func (n *node) Add(child *node) *v2error.Error {
	// 检测当前节点是否为目录节点
	if !n.IsDir() {
		return v2error.NewError(v2error.EcodeNotDir, "", n.store.CurrentIndex)
	}
	// 按照“／”进行切分，得到待添加子节点对应的key
	_, name := path.Split(child.Path)
	// 检测当前节点的Child字段中是否已存在待添加子节点
	if _, ok := n.Children[name]; ok {
		return v2error.NewError(v2error.EcodeNodeExist, "", n.store.CurrentIndex)
	}

	n.Children[name] = child	// 添加子节点

	return nil
}

// Remove（）方法负责将当前节点从其父节点中删除，其中会根据参数决定是否递归删除当前节点的子节点，
func (n *node) Remove(dir, recursive bool, callback func(path string)) *v2error.Error {
	if !n.IsDir() { // 当前节点为KV节点
		_, name := path.Split(n.Path)	// 获取当前节点对应的Key
		// 查找当前节点的父节点，并将当前节点从父节点的Child字段中删除
		if n.Parent != nil && n.Parent.Children[name] == n {
			delete(n.Parent.Children, name)
		}

		if callback != nil {	// 回调callback函数
			callback(n.Path)
		}
		// 当前节点为非永久节点，则将其从store.ttlKeyHeap中删除，
		// store.ttlKeyHeap中的节点是按照过期时间排序的，
		if !n.IsPermanent() {
			n.store.ttlKeyHeap.remove(n)
		}

		return nil
	}
	// 下面是针对目录节点的删除操作
	// 只有dir参数设立为true，才能删除项目录节点
	if !dir {
		return v2error.NewError(v2error.EcodeNotFile, n.Path, n.store.CurrentIndex)
	}
	// 如果当前目录节点还存在子节点，且不能进行逆归删除（recursive参数设置为false），则不能删除该目录节点
	if len(n.Children) != 0 && !recursive {
		return v2error.NewError(v2error.EcodeDirNotEmpty, n.Path, n.store.CurrentIndex)
	}
	// 逆归删除当前目录节点的全部子节点
	for _, child := range n.Children { // 删除所有子目录
		child.Remove(true, true, callback)
	}

	// 下面是删除的当前节点本身，
	_, name := path.Split(n.Path)
	if n.Parent != nil && n.Parent.Children[name] == n {
		delete(n.Parent.Children, name)

		if callback != nil {
			callback(n.Path)
		}

		if !n.IsPermanent() {
			n.store.ttlKeyHeap.remove(n)
		}
	}

	return nil
}

// node.Repr（）方法中，会将当前节点和子节点（根据参数决定是否递归处理子节点以及子节点是否排序）转换成NodeExtern实例返回
func (n *node) Repr(recursive, sorted bool, clock clockwork.Clock) *NodeExtern {
	if n.IsDir() {	// 下面是针对目录节点的处理
		node := &NodeExtern{	// NodeExtern是node的外部表示形式
			Key:           n.Path,
			Dir:           true,
			ModifiedIndex: n.ModifiedIndex,
			CreatedIndex:  n.CreatedIndex,
		}
		// 计算当前节点的过期时间和TTL（即当前节点还能存活多长时间）
		node.Expiration, node.TTL = n.expirationAndTTL(clock)

		if !recursive {	// recursive参数表示是否递归获取子节点
			return node
		}

		children, _ := n.List()	// 获取子节点
		node.Nodes = make(NodeExterns, len(children))
		i := 0
		for _, child := range children {	// 边历子节点
			if child.IsHidden() { // 忽略隐藏节点
				continue
			}
			// 调用子节点的Repr（）方法，创建对应的NodeExtern实例
			node.Nodes[i] = child.Repr(recursive, sorted, clock)

			i++
		}

		// 这里简羊进行压缩，释放隐藏节点导致的空间浪费
		node.Nodes = node.Nodes[:i]
		if sorted {	// 根据sorted参敛，决定是否对子节点进行排序
			sort.Sort(node.Nodes)
		}

		return node
	}

	// 下面是针对KV节点的处理
	value := n.Value	// 复制当前节点的Value值
	node := &NodeExtern{	// 创建当前节点对应的NodeExtern实例，并初始化相反字段
		Key:           n.Path,
		Value:         &value,
		ModifiedIndex: n.ModifiedIndex,
		CreatedIndex:  n.CreatedIndex,
	}
	// 计算当前节点的过期时间和TTL
	node.Expiration, node.TTL = n.expirationAndTTL(clock)
	return node
}

// UpdateTTL（）方法，该方法会更新指定节点的过期时间，另外还会更新该节点在TTLKeyHeap中的排序
func (n *node) UpdateTTL(expireTime time.Time) {
	if !n.IsPermanent() {	// 对非永久节点的处理
		if expireTime.IsZero() {
			n.ExpireTime = expireTime	// 更新当前节点的过期时间
			n.store.ttlKeyHeap.remove(n)
			return
		}
		// 更新当前节点的过期时间
		n.ExpireTime = expireTime
		// 更新当前节点在TTLKeyHeap中排序
		n.store.ttlKeyHeap.update(n)
		return
	}

	if expireTime.IsZero() {
		return
	}
	// 下面是将永久节点变成非永久节点
	n.ExpireTime = expireTime
	// 将当前节点添加到TTLKeyHeap中
	n.store.ttlKeyHeap.push(n)
}

// 比较函数将节点索引和值与提供的。
// 第二个结果值解释结果并等于比较中的一个。。常量
func (n *node) Compare(prevValue string, prevIndex uint64) (ok bool, which int) {
	indexMatch := prevIndex == 0 || n.ModifiedIndex == prevIndex
	valueMatch := prevValue == "" || n.Value == prevValue
	ok = valueMatch && indexMatch
	switch {
	case valueMatch && indexMatch:
		which = CompareMatch
	case indexMatch && !valueMatch:
		which = CompareValueNotMatch
	case valueMatch && !indexMatch:
		which = CompareIndexNotMatch
	default:
		which = CompareNotMatch
	}
	return ok, which
}

// 克隆函数递归克隆节点并返回新节点。
// 如果节点是目录，则会克隆该目录下的所有内容。
// 如果节点是一个键值对，它将克隆该对。
func (n *node) Clone() *node {
	if !n.IsDir() {
		newkv := newKV(n.store, n.Path, n.Value, n.CreatedIndex, n.Parent, n.ExpireTime)
		newkv.ModifiedIndex = n.ModifiedIndex
		return newkv
	}

	clone := newDir(n.store, n.Path, n.CreatedIndex, n.Parent, n.ExpireTime)
	clone.ModifiedIndex = n.ModifiedIndex

	for key, child := range n.Children {
		clone.Children[key] = child.Clone()
	}

	return clone
}

// recoverAndclean函数有助于执行恢复。
// 需要做两件事：1。恢复结构；2.删除过期节点
// 
// 如果节点是目录，将帮助恢复子节点的父指针，并递归
// 对其子节点调用此函数。
// 由于需要首先恢复整个结构并添加所有
// 事件历史记录中的通知。
func (n *node) recoverAndclean() {
	if n.IsDir() {
		for _, child := range n.Children {
			child.Parent = n
			child.store = n.store
			child.recoverAndclean()
		}
	}

	if !n.ExpireTime.IsZero() {
		n.store.ttlKeyHeap.push(n)
	}
}
